This invention relates generally to the field of digital communications and more particularly to systems and methods for switching packets of data in a switching node used in a digital data network and for monitoring data flow at the switching node.
Digital networks have been developed to facilitate the transfer of information including data and programs among digital computer systems and numerous other types of devices. A variety of types of networks have been developed and implemented using diverse information transfer methodologies. In modern networks, information is transferred through a mesh of switching nodes which are interconnected by communication links in a variety of patterns. The mesh interconnection pattern can allow for a number of paths to be available through the network from each computer system or other device to another computer system or other device.
Information transferred from a source device to a destination device is generally transferred in the form of fixed or variable-length data packets, each of which is in general received by a switching node over a communication link and transmitted over another communication link to facilitate transfer of the packet to the destination device or to another switching node along a path to the destination device. Each packet typically includes address information including a source address that identifies the device that generated the packet and a destination address that identifies the particular device or devices which are to receive the packet.
Typically, a switching node includes one or more input ports, each of which is connected to a communication link on the network to receive data packets, and one or more output ports, each of which is also connected to a communication link on the network to transmit packets. Each node typically also includes a switching fabric that couples data packets from the input ports to the output ports for transmission.
Typically, a network service provider maintains and operates one or more switching nodes which can transfer data packets from input communication links across the switching fabric to output communication links. These providers charge fees to customers who use the links to transfer data across the nodes on the network. Typically, the fees are related to the maximum data rate at which a customer can expect data to be forwarded across the node.
Each link at a node is typically assigned at least one xe2x80x9cclass of servicexe2x80x9d which is related to a maximum allowable data rate provided to a customer that uses the link, which in turn is based upon the fee paid by the customer to the provider. In many cases, each link can be assigned multiple classes of service associated with a single user or multiple users.
It is in the interest of service providers to monitor or xe2x80x9cpolicexe2x80x9d data traffic on each link to determine whether customers"" use of their allocated links is within contractual limits. Where it is determined that the use of the link, i.e., the data rate, exceeds the contractual limit, data packets can be identified and marked as such, i.e., as being xe2x80x9cout of contract.xe2x80x9d In many cases, it is important to carefully monitor data traffic on each link at each class of service. It is also often desirable to mark data packets with respect to the degree to which a particular packet may be out of contract. For example, if a particular packet is only slightly out of contract, it may be desirable to mark the packet as such. Also, in cases of extreme overuse of the link, it may also be desirable that data packets be so marked.
In some systems, the degree to which a packet exceeds the link contract data rate is used to set a priority for discarding the packet. Packets that only slightly exceed the contract rate are assigned relatively low xe2x80x9cdiscard eligibilityxe2x80x9d values, while packets that greatly exceed the maximum rate are assigned high discard eligibility values. In the event that it becomes necessary to drop a particular packet, those with higher discard eligibility values are more likely to be dropped than those with lower discard eligibility values.
Several approaches have been employed to monitor data flow rates on multiple links having multiple classes of service. One common approach is referred to as a xe2x80x9cleaky bucketxe2x80x9d approach. Under this approach, a memory or register storage location, commonly referred to as a xe2x80x9cbucket,xe2x80x9d is allocated to each link and class of service. Each storage location or bucket maintains a count of a number of data units received for its assigned link and class of service. A data unit can be a byte of data, or a group of data bytes for example, where each data packet transfers multiple bytes of data. For each bucket, a predetermined threshold number of data units, related to the maximum allowable data rate for the associated link and class of service, is generated and stored. As a data packet is received, the number of data units (bytes) is added to the present value or count in the bucket, and the updated value is compared to the threshold. If the updated value exceeds the threshold, then the incoming data packet is marked as exceeding the threshold. Because it is data rates that are being policed rather than the total amount of data received, the value or count stored in each bucket is periodically decremented a predetermined number of data units related to the maximum allowable data rate and the period at which the decrementing takes place. This decrementing is commonly referred to as xe2x80x9cleakingxe2x80x9d the bucket. By leaking the bucket at the correct predetermined rate, it is ensured that when the number of data units in the bucket exceeds the predetermined threshold, the maximum allowable data rate has been exceeded.
In order to identify short bursts of large amounts of data that exceed the maximum allowable data rate, it is desirable to leak each bucket and perform a threshold comparison as often as possible. Such short bursts can be missed where buckets are not leaked and checked often enough. In relatively small systems, having a relatively small number of buckets, the system can cycle through all of the buckets relatively quickly such that short bursts of large amounts of data can be identified as being out of contract. In such systems, the buckets take the form of memory locations and the leaking and checking is performed in the system software. However, as systems become larger with larger numbers of links and classes of service and, consequently, larger numbers of buckets, the leaking and checking periods for each bucket become longer. Thus, the buckets are not maintained as frequently, and the likelihood of not identifying short large data bursts increases. Thus, the data rate policing in such systems becomes less accurate.
The present invention is directed to an apparatus and method for monitoring or policing data traffic at a network node which facilitates data transfer on at least one link having at least one class of service. The data are transferred in data packets, and each data packet includes at least one unit of data. For each of at least one selected link and class of service, an updatable value is stored in a storing device. A counter value in a counter is incremented at a rate determined by a maximum allowable data rate associated with the selected link and class of service. A data packet is received and a number of units of data in the data packet is counted. An adjusted updatable value is computed by adjusting the updatable value according to the counter value at the time the data packet was received and the number of units of data in the data packet. The adjusted updatable value is compared to a predetermined threshold associated with the selected link and class of service. The data packet is marked with respect to the allowable data rate based on whether the adjusted updatable value exceeds the predetermined threshold.
In one embodiment, the adjusted updatable value is computed by computing a difference between the updatable value and the counter value when the data packet was received. Next, that computed difference can be added to the number of units of data in the received data packet to compute the adjusted updatable value. In one embodiment, the adjusted updatable value is used to update the updatable value, such as by adding the adjusted updatable value to the number of units of data in the data packet and storing the resulting sum back in the storing unit as the updated value.
In one embodiment, each link can include multiple classes of service, and each class of service can have a unique allowable data rate. As a result, the storing device can include multiple individual storage areas. For example, the storing device can be a semiconductor memory, such as a static random access memory (SRAM), having multiple addressable locations. Therefore, the storing device stores a plurality of updatable values for each of a plurality of links and/or a plurality of classes of service.
In one embodiment, each data packet is associated with a discard eligibility value, which identifies a priority for discarding the data packet. In general, packets assigned higher discard eligibility values are more likely to be discarded if it is determined that discard is necessary for reasons such as excess data traffic or congestion. Therefore, in the present invention, data packets can be marked according to whether they cause a threshold to be exceeded by altering the discard eligibility value for the packet. That is, if a packet causes a threshold to be exceeded, the discard eligibility can be increased such that the priority for discard of the packet is increased.
In one embodiment of the invention, a link and class of service can be assigned multiple predetermined thresholds such that the discard eligibility value can be set to one of multiple corresponding levels, depending upon which of the thresholds are exceeded. In one embodiment, additional storing devices are provided to allow for multiple-stage policing such that multiple discard eligibility levels can be assigned. Where a second storing device is provided, a second updatable value associated with the selected link and class of service is stored in the second storing device. A second adjustable updatable value is computed according to the counter value at the time the data packet was received and the number of units data in the data packet. The second adjusted updatable value is compared to a second predetermined threshold associated with the selected link and class of service, where the second predetermined threshold is chosen to identify a second level of discard eligibility for packets. The incoming data packet is marked with respect to the allowable data rate based on whether the second adjusted updatable value exceeds the second predetermined threshold. In one embodiment, data packets are analyzed with respect to the second and other further stages if the packet is found to cause the first predetermined threshold to be exceeded.
Hence, in the present invention, a single counter is effectively used to effectively decrement the values stored in all of the xe2x80x9cbucketsxe2x80x9d simultaneously. This single counter can be applied to counter derivation circuitry to derive counter values for any number of the buckets for any number of the links and classes of service. In the present invention, the processing stages, the buckets, which can be implemented as semiconductor SRAM memories, the counter and counter derivation circuitry can all be implemented in hardware. As a result, periodic round-robin decrementing or xe2x80x9cleaking,xe2x80x9d as found in prior leaky bucket systems, is eliminated. Bucket values can be decremented and checked over extremely small time intervals such that large bursts in short time periods can be identified. The result is a much more precise and accurate policing approach than was found in prior systems. Because of the high precision of the policing approach of the invention, it can be applied in very large systems having large numbers of links and classes of service.
The invention is applicable in various networks in which it is desirable to monitor data traffic on links. For example, the invention can be implemented in a switching node such as the one described in co-pending U.S. patent application Ser. No. 09/108,771, filed on Jul. 2, 1998, entitled xe2x80x9cSystem and Method for Switching Packets in a Network,xe2x80x9d by Schwartz, et al., and assigned to the same assignee as the present application. The contents of that application are incorporated herein in their entirety by reference.